题解 AT359@洛谷 | 359@Atcoder 【団子とうさぎ】

C++、C、Python三语言题解

首先,Σi=1ni2=n(n+1)(2n+1)/6\Sigma_{i=1}^{n}i^2=n(n+1)(2n+1)/6,这一点可以通过数论证明。然后套公式即可,时间复杂度O(1)O(1)

C++语言

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin>>a>>b;
    int r = a * (a + 1) * (2 * a + 1) / 6;
    cout<<r%b<<endl;
    return 0;
}

C语言

#include <stdio.h>

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    int r = a * (a + 1) * (2 * a + 1) / 6;
    printf("%d", r%b);
    return 0;
}

Python

a=int(input())
print(a*(a+1)*(2*a+1)//6%int(input()))